package listbyorder.access101_200.test130;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/10 9:14
 */
public class Solution2 {

    // 方法二，从外边向里面作DFS
    public void solve(char[][] board) {
        int row = board.length;
        int col = board[0].length;
        if (row < 3 || col < 3) return;
        boolean[][] visited = new boolean[row][col];

        // 从边界开始作DFS
        for (int i = 0; i < col; i++) {
            if (board[0][i] == 'O') {
                dfs(0, i, visited, board);
            }
            // 最下面一行作dfs
            if (board[row - 1][i] == 'O') {
                dfs(row - 1, i, visited, board);
            }
        }

        for (int i = 1; i < row - 1; i++) {
            if (board[i][0] == 'O') {
                dfs(i, 0, visited, board);
            }
            if (board[i][col - 1] == 'O') {
                dfs(i, col - 1, visited, board);
            }
        }

        // 把所有没有标记过的O改为X
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (!visited[i][j] && board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    private void dfs(int r, int c, boolean[][] visited, char[][] board) {
        if (r < 0 || c < 0 || r == board.length || c == board[0].length) {
            return;
        }
        if (visited[r][c]) {
            return;
        }
        if (board[r][c] == 'O') {
            visited[r][c] = true;
            dfs(r + 1, c, visited, board);
            dfs(r - 1, c, visited, board);
            dfs(r, c + 1, visited, board);
            dfs(r, c - 1, visited, board);
        }
    }
}
